import java.io.*;
import java.util.*;

public abstract class PathAlg {
	// Result
	protected float expectedLatency = -1;
	protected int[] path = null;
	protected long time = -1;

	// Graph
	protected float[] probabilities  = null;
	protected int[][] costs = null;

	public abstract void runAlgorithm();
	public abstract String getName();

	public long runAlgorithmTimed()
	{
		long t = Calendar.getInstance().getTimeInMillis();
		runAlgorithm();
		this.time = Calendar.getInstance().getTimeInMillis() - t;

		return this.time;
	}
	
	public void buildGraph(String inputFile)
	{
		// Parse file and set up graph
		BufferedReader in;

		try
		{
			in = new BufferedReader(new FileReader(inputFile));
		}
		catch(FileNotFoundException ex)
		{
			System.err.println("File \"" + inputFile + "\" not found.");
			return;
		}
		
		String line;
		try
		{
			int i = 0;
			int numNodes = 0;
			while((line = in.readLine()) != null)
			{
				// First line should contain our array lengths
				if(i == 0)
				{
					numNodes = Integer.parseInt(line);
					costs = new int[numNodes][numNodes];
					probabilities = new float[numNodes];

					path = new int[numNodes];
					// Always visit first node first
					this.path[0] = 0;
				}
				// The next numNodes lines should contain probabilities
				else if(i <= numNodes)
				{
					probabilities[i-1] = Float.parseFloat(line);
				}
				// And the rest should hold our cost matrix
				else
				{
					String[] nums = line.split(" ");
					for(int j=0; j<nums.length; ++j)
					{
						costs[i-1-numNodes][j] = Integer.parseInt(nums[j]);
					}
				}
				i = i + 1;
			}
		}
		catch(IOException ex)
		{
			System.err.println("Error when reading file.");
		}
	}

	public int[] getPath()
	{
		if(this.path == null)
		{
			throw new IllegalStateException("Algorithm has not been run");
		}

		return this.path;
	}

	protected float calculateExpectedLatency(int[] path)
	{
		float sum = 0;
		int pathCost = 0;
		int lastNode = 0;
		for(int v : path)
		{
			// Do not need to calculate first step 
			if(v == 0)
			{
				continue;
			}

			pathCost += costs[lastNode][v];
			sum += probabilities[v]*pathCost;

			lastNode = v;
		}

		return sum;
	}

	public float getExpectedLatency()
	{
		if(this.path == null)
		{
			throw new IllegalStateException("Algorithm has not been run");
		}

		if(this.expectedLatency < 0)
		{
			this.expectedLatency = calculateExpectedLatency(this.path);
		}

		return this.expectedLatency;
	}

	public long getTime()
	{
		if(this.time < 0)
			throw new IllegalStateException("Timed algorithm not run.");

		return this.time;
	}
}
